package java0330;

class HashNode {
    public int key;
    public int value;
    public HashNode next;

    public HashNode(int key, int value) {
        this.key = key;
        this.value = value;
    }
}

public class MyHashMap {
    // 哈希表
    private HashNode[] array = new HashNode[8];
    // 表中的元素个数
    private int size = 0;

    // 哈希函数,简单求余
    private int hash(int key) {
        // 可以设计的更为复杂,比如根据 key 计算 md5 在求余
        return key % array.length;
    }

    // 根据 key 的值查找 value
    public Integer get(int key) {
        int index = hash(key);
        for (HashNode cur = array[index]; cur != null; cur = cur.next) {
            if (cur.key == key) {
                // 找到了
                return cur.value;
            }
        }
        return null;
    }

    // 根据 key 的值查找 value
    // 如果查找不到，返回默认值
    public Integer getOrDefault(int key, int defaultVal) {
        Integer ret = get(key);
        if (ret == null) {
            return defaultVal;
        }
        return ret;
    }

    // 插入新的键值对
    public void put(int key, int value) {
        int index = hash(key);
        if (array[index] == null) {
            // 如果这个位置还没有元素
            array[index] = new HashNode(key, value);
        }else {
            // 这个位置已经有元素了,即发生哈希冲突,
            // 我们先在这个位置的链表查找存不存在该 key 值
            for (HashNode cur = array[index]; cur != null; cur = cur.next) {
                if (cur.key == key) {
                    // 这个 key 已经存在了,现在修改这个 value 即可
                    cur.value = value;
                    return;
                }
            }
            // 循环结束也没有发现和 key 相等的,新建节点,头插在此
            HashNode newNode = new HashNode(key, value);
            newNode.next = array[index];
            array[index] = newNode;
        }
        size++;
        // 到这里插入已经成功了
        // 但是可能疯狂插入导致每个链表都很长,使得查找的效率低下,
        // 所以当哈希表拥挤到一定程度的时候我们要进行扩容
        // loadFactor() 是负载因子 = 元素个数 / 数组长度
        if (loadFactor() > 0.5) {
            // 扩容
            resize();
        }
        return;
    }

    private void resize() {
        // 使用更大的数组存放
        HashNode[] newArray = new HashNode[2 * array.length];
        // 搬运旧表上的元素
        for (int i = 0; i < array.length; i++) {
            HashNode next = null;
            for (HashNode cur = array[i]; cur != null; cur = next) {
                next = cur.next;
                int index = cur.key % newArray.length;
                // 插入新表
//                if (newArray[index] == null) {
//                    newArray[index] = cur;
//                }else {
                    cur.next = newArray[index];
                    newArray[index] = cur;
//                }
            }
        }
        array = newArray;
    }

    private double loadFactor() {
        return (double) size / array.length;
    }

    // 根据 key 的值删除对应的键值对
    // 删除成功返回 key 对应的 value ，失败返回 null
    public Integer remove(int key) {
        int index = hash(key);
        Integer ret = null;
        if (array[index] == null) {
            // 这个链表直接为空,查找失败
            return null;
        }
        if (array[index].key == key) {
            // 说明待删除的节点是链表头结点
            ret = array[index].value;
            array[index] = array[index].next;
            size--;
            return ret;
        }
        // 待删除的节点可能在中间某个位置
        HashNode pre = null;
        for (HashNode cur = array[index]; cur != null; pre = cur, cur = cur.next) {
            if (cur.key == key) {
                // 找到了
                ret = cur.value;
                pre.next = cur.next;
                size--;
                return ret;
            }
        }
        // 循环结束都没找到,说明没有
        return null;
    }

    public static void main(String[] args) {
        MyHashMap myHashMap = new MyHashMap();
        myHashMap.put(1,1);
        myHashMap.put(9,9);
        myHashMap.put(17,17);
        myHashMap.put(25,25);
        myHashMap.put(33,33);
        myHashMap.put(41,41);
        myHashMap.put(49,49);
        myHashMap.put(57,57);
//        myHashMap.put(134,134);
//        myHashMap.put(156,156);
//        System.out.println(myHashMap.get(5));
//        System.out.println(myHashMap.get(12));
//        System.out.println(myHashMap.get(15));
//        System.out.println(myHashMap.get(156));
        System.out.println("删除");
//        System.out.println(myHashMap.remove(134));
//        System.out.println(myHashMap.remove(1));
//        System.out.println(myHashMap.remove(12));
//        System.out.println(myHashMap.remove(199));
//        System.out.println(myHashMap.get(134));
//        System.out.println(myHashMap.get(1));
//        System.out.println(myHashMap.get(12));

    }
}
